/*
 * Copyright (c) 2022 Hong Jiahua
 * https://gitee.com/arrco/jh_static_set
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
/**
  * @file        jh_static_set.c
  * @brief       集合
  * @details     集合
  * @author      Hong Jiahua
  * @version     1.0.0
  * @date        2022-08-14
  * @copyright   2022 Hong Jiahua MIT License
  */
#include <stdio.h>
#include "jh_static_set.h"

/************************************************************************/
/*                                                                      */
/************************************************************************/
#include <string.h>

#define JH_SET_MEMCPY   memcpy
/************************************************************************/
/*                                                                      */
/************************************************************************/
#define JH_SS_GET(__set, __node, __val) ((jh_static_set_node_t *)((__set)->base + (__node) * (__set)->size + (__set)->offset))->__val
#define JH_SS_SUBGET(__set, __node, __val, __subval) JH_SS_GET(__set, JH_SS_GET(__set, __node, __val), __subval)
#define JH_SS_GET_ELEMENT(__set, __node) ((void *)((__set)->base + (__node) * (__set)->size + (__set)->dataoffset))
#define JH_SS_END(__set) ((__set)->num - 1)
#define JH_SS_IDLE_HEAD 0
#define JH_SS_NULL      0

#define JH_SS_HEIGHT(__set, __node) (((__node) != JH_SS_NULL) ? (JH_SS_GET((__set), (__node), height)) : -1)
#define JH_SS_HEAVY(__set, __node1, __node2) ((JH_SS_HEIGHT((__set), (__node1)) - JH_SS_HEIGHT((__set), (__node2))) == 2)
#define JH_SS_MAX(x, y) ((x) > (y) ? (x) : (y))
#define JH_SS_LEFT_CHILD 1
#define JH_SS_RIGHT_CHILD 2

#define JH_SSS_GET(__node, __val)               JH_SS_GET(set, __node, __val)
#define JH_SSS_SUBGET(__node, __val, __subval)  JH_SS_SUBGET(set, __node, __val, __subval)
#define JH_SSS_GET_ELEMENT(__node)              JH_SS_GET_ELEMENT(set, __node)
#define JH_SSS_END                              JH_SS_END(set)
#define JH_SSS_HEIGHT(__node)                   (((__node) != JH_SS_NULL) ? (JH_SSS_GET((__node), height)) : -1)
#define JH_SSS_HEAVY(__node1, __node2)          JH_SS_HEAVY(set, __node1, __node2)

/************************************************************************/
/*                                                                      */
/************************************************************************/
#define SGET(__node, __val)             JH_SSS_GET(__node, __val)
#define SSGET(__node, __val, __subval)  JH_SSS_SUBGET(__node, __val, __subval)
#define SGETE(__node)                   JH_SSS_GET_ELEMENT(__node)
#define SEND                            JH_SSS_END
#define SIDLEHEAD                       JH_SS_IDLE_HEAD
#define SNULL                           JH_SS_NULL
#define SHEIGHT(__node)                 JH_SSS_HEIGHT(__node)
#define SHEAVY(__node1, __node2)        JH_SSS_HEAVY(__node1, __node2)
#define SMAX(x, y)                      JH_SS_MAX(x, y)
#define SLEFTCHILD                      JH_SS_LEFT_CHILD
#define SRIGHTCHILD                     JH_SS_RIGHT_CHILD
/************************************************************************/
/*                                                                      */
/************************************************************************/
/*查找最小节点*/
static jh_static_set_node_type jh_static_set_min(jh_static_set_t* set, jh_static_set_node_type node) {
    if(node == SNULL)
        return SNULL;

    while(SGET(node, left) != SNULL)
        node = SGET(node, left);
    return node;
}

/*查找最大节点*/
static jh_static_set_node_type jh_static_set_max(jh_static_set_t* set, jh_static_set_node_type node) {
    if(node == SNULL)
        return SNULL;

    while(SGET(node, right) != SNULL)
        node = SGET(node, right);
    return node;
}

/*LL rotation - LL旋转*/
static jh_static_set_node_type jh_static_set_left_left_rotation(jh_static_set_t* set, jh_static_set_node_type node) {
    jh_static_set_node_type nodeleft = SGET(node, left);
    jh_static_set_node_type parent = SGET(node, parent);
    
    SGET(node, left) = SGET(nodeleft, right);
    if(SGET(nodeleft, right))
        SSGET(nodeleft, right, parent) = node;
    SGET(nodeleft, right) = node;
    SGET(node, parent) = nodeleft;
    SGET(nodeleft, parent) = parent;
    if(parent) {
        if(SGET(parent, left) == node) {
            SGET(parent, left) = nodeleft;
        } else {
            SGET(parent, right) = nodeleft;
        }
    }

    SGET(node, height) = SMAX( SHEIGHT(SGET(node, left)), SHEIGHT(SGET(node, right))) + 1;
    SGET(nodeleft, height) = SMAX( SHEIGHT(SGET(nodeleft, left)), SGET(node, height)) + 1;

    return nodeleft;
}

/*RR rotation - RR旋转*/
static jh_static_set_node_type jh_static_set_right_right_rotation(jh_static_set_t* set, jh_static_set_node_type node) {
    jh_static_set_node_type noderight = SGET(node, right);
    jh_static_set_node_type parent = SGET(node, parent);
    
    SGET(node, right) = SGET(noderight, left);
    if(SGET(noderight, left))
        SSGET(noderight, left, parent) = node;
    SGET(noderight, left) = node;
    SGET(node, parent) = noderight;
    SGET(noderight, parent) = parent;
    if(parent) {
        if(SGET(parent, left) == node) {
            SGET(parent, left) = noderight;
        } else {
            SGET(parent, right) = noderight;
        }
    }

    SGET(node, height) = SMAX( SHEIGHT(SGET(node, left)), SHEIGHT(SGET(node, right))) + 1;
    SGET(noderight, height) = SMAX( SHEIGHT(SGET(noderight, right)), SGET(node, height)) + 1;

    return noderight;
}

/*LR rotation - LR旋转*/
static jh_static_set_node_type jh_static_set_left_right_rotation(jh_static_set_t* set, jh_static_set_node_type node) {
    jh_static_set_right_right_rotation(set, SGET(node, left));
    return jh_static_set_left_left_rotation(set, node);
}

/*RL rotation - RL旋转*/
static jh_static_set_node_type jh_static_set_right_left_rotation(jh_static_set_t* set, jh_static_set_node_type node) {
    jh_static_set_left_left_rotation(set, SGET(node, right));
    return jh_static_set_right_right_rotation(set, node);
}

/*搜索节点*/
static jh_static_set_node_type jh_static_set_search(jh_static_set_t* set, jh_static_set_node_type node, void* value) {
    if(node == SNULL)
        return node;
    
    int ret = set->compare(value, SGETE(node));
    
    while (ret != 0) {
        node = ret < 0 ? SGET(node, left) : SGET(node, right);
        if(node == SNULL)
            break;
        
        ret = set->compare(value, SGETE(node));
    }

    return node;
}

/*创建节点*/
static jh_static_set_node_type jh_static_set_create_node(jh_static_set_t* set, void* value) {
    jh_static_set_node_type node = SGET(SIDLEHEAD, right);
    
    if(node) {
        SGET(SIDLEHEAD, right) = SGET(node, right);
        
        JH_SET_MEMCPY(SGETE(node), value, set->datasize);
        SGET(node, height) = 0;
        SGET(node, parent) = SNULL;
        SGET(node, left)   = SNULL;
        SGET(node, right)  = SNULL;
    }
    
    return node;
}

/*销毁节点*/
static void jh_static_set_destroy_node(jh_static_set_t* set, jh_static_set_node_type node) {
    SGET(node, right) = SGET(SIDLEHEAD, right);
    SGET(SIDLEHEAD, right) = node;
}

/*添加数据*/
static jh_static_set_node_type jh_static_set_add(jh_static_set_t* set, jh_static_set_node_type node, void* value) {
    jh_static_set_node_type parenttree = SNULL;
    int ret = 0;
    
    while(1) {
        if(node == SNULL) {
            node = jh_static_set_create_node(set, value);
            if(node == SNULL)
                return SNULL;
            
            if(parenttree) {
                SGET(node, parent) = parenttree;
                
                if(ret < 0) {
                    SSGET(node, parent, left) = node;
                } else if(ret > 0) {
                    SSGET(node, parent, right) = node;
                }
            }
            
            break;
        }
        
        ret = set->compare(value, SGETE(node));
        parenttree = node;
        if(ret == 0)
            return SNULL;
        
        node = ret < 0 ? SGET(node, left) : SGET(node, right);
    }
    
    while(1) {
        if(SGET(node, parent) == SNULL)
            break;
        
        if(SSGET(node, parent, left) == node) {
            node = SGET(node, parent);
            if(SHEAVY(SGET(node, left), SGET(node, right))) {
                node = set->compare(value, SGETE(SGET(node, left))) < 0 ? jh_static_set_left_left_rotation(set, node) : jh_static_set_left_right_rotation(set, node);
            }
        } else if(SSGET(node, parent, right) == node) {
            node = SGET(node, parent);
            if(SHEAVY(SGET(node, right), SGET(node, left))) {
                node = set->compare(value, SGETE(SGET(node, right))) > 0 ? jh_static_set_right_right_rotation(set, node) : jh_static_set_right_left_rotation(set, node);
            }
        }
       SGET(node, height) = SMAX( SHEIGHT(SGET(node, left)), SHEIGHT(SGET(node, right))) + 1;
    }
    
    return node;
}

/*删除数据*/
static jh_static_set_node_type jh_static_set_delete(jh_static_set_t* set, jh_static_set_node_type node, void* value) {
    void* targetvalue = value;
    int dir = 0, ret = 0;
    
    while(1) {
        if(node == SNULL)
            return SNULL;
        
        ret = set->compare(targetvalue, SGETE(node));
        if(ret < 0) {
            node = SGET(node, left);
            dir = SLEFTCHILD;
        } else if(ret > 0) {
            node = SGET(node, right);
            dir = SRIGHTCHILD;
        } else {
            if((SGET(node, left)) && (SGET(node, right))) {
                if(SHEIGHT(SGET(node, left)) > SHEIGHT(SGET(node, right))) {
                    jh_static_set_node_type max = jh_static_set_max(set, SGET(node, left));
                    JH_SET_MEMCPY(SGETE(node), SGETE(max), set->datasize);
                    targetvalue = SGETE(node);
                    node = SGET(node, left);
                    dir = SLEFTCHILD;
                } else {
                    jh_static_set_node_type min = jh_static_set_min(set, SGET(node, right));
                    JH_SET_MEMCPY(SGETE(node), SGETE(min), set->datasize);
                    targetvalue = SGETE(node);
                    node = SGET(node, right);
                    dir = SRIGHTCHILD;
                }
                continue;
            } else {
                jh_static_set_node_type delnode = node;
                node = SGET(node, left) ? : SGET(node, right);
                if(node) {
                    SGET(node, parent) = SGET(delnode, parent);
                    if(dir == SLEFTCHILD) {
                        SSGET(node, parent, left) = node;
                    } else if(dir == SRIGHTCHILD) {
                        SSGET(node, parent, right) = node;
                    }
                } else {
                    if(dir == SLEFTCHILD) {
                        SSGET(delnode, parent, left) = SNULL;
                        node = SGET(delnode, parent);
                        if(SHEAVY(SGET(node, right), SGET(node, left))) {
                            node = SHEIGHT(SSGET(node, right, left)) > SHEIGHT(SSGET(node, right, right)) ? jh_static_set_right_left_rotation(set, node) : jh_static_set_right_right_rotation(set, node);
                        }
                        SGET(node, height) = SMAX(SHEIGHT(SGET(node, left)), SHEIGHT(SGET(node, right))) + 1;
                    } else if(dir == SRIGHTCHILD) {
                        SSGET(delnode, parent, right) = SNULL;
                        node = SGET(delnode, parent);
                        if(SHEAVY(SGET(node, left), SGET(node, right))) {
                            node = SHEIGHT(SSGET(node, left, right)) > SHEIGHT(SSGET(node, left, left)) ? jh_static_set_left_right_rotation(set, node) : jh_static_set_left_left_rotation(set, node);
                        }
                        SGET(node, height) = SMAX(SHEIGHT(SGET(node, left)), SHEIGHT(SGET(node, right))) + 1;
                    } else {
                        node = SGET(delnode, parent);
                    }
                }
                jh_static_set_destroy_node(set, delnode);
                break;
            }
        }
    }
    
    while(1) {
        if(node == SNULL || SGET(node, parent) == SNULL) {
            break;
        }
        
        if(SSGET(node, parent, left) == node) {
            node = SGET(node, parent);
            if(SHEAVY(SGET(node, right), SGET(node, left))) {
                node = SHEIGHT(SSGET(node, right, left)) > SHEIGHT(SSGET(node, right, right)) ? jh_static_set_right_left_rotation(set, node) : jh_static_set_right_right_rotation(set, node);
            }
        } else if(SSGET(node, parent, right) == node) {
            node = SGET(node, parent);
            if(SHEAVY(SGET(node, left), SGET(node, right))) {
                node = SHEIGHT(SSGET(node, left, right)) > SHEIGHT(SSGET(node, left, left)) ? jh_static_set_left_right_rotation(set, node) : jh_static_set_left_left_rotation(set, node);
            }
        }
        SGET(node, height) = SMAX(SHEIGHT(SGET(node, left)), SHEIGHT(SGET(node, right))) + 1;
    }

    return node;
}

/*销毁集合*/
static void jh_static_set_destroy(jh_static_set_t* set, jh_static_set_node_type node) {
    jh_static_set_node_type delnode;
    
    while(node) {
        while(SGET(node, left)) {
            node = SGET(node, left);
        }
        if(SGET(node, right)) {
            node = SGET(node, right);
            continue;
        }

        delnode = node;
        node = SGET(node, parent);
        if(node) {
            if(SGET(node, left) == delnode)
                SGET(node, left) = SNULL;
            else if(SGET(node, right) == delnode)
                SGET(node, right) = SNULL;
        }
        jh_static_set_destroy_node(set, delnode);
    }

    return;
}

/************************************************************************/
/*                                                                      */
/************************************************************************/
/**
  * @brief      从集合的节点中获取数据
  * @param[in]  set         集合
  * @param[in]  usernode    数据结点
  * @param[out] value       数据项
  *
  * @return     无
  */
void jh_static_set_memcpy(jh_static_set_t* set, jh_static_set_node_type usernode, void* value) {
    JH_SET_MEMCPY(value, SGETE(usernode), set->datasize);
}

/**
  * @brief      在集合中查找下一个数据
  * @param[in]  set         集合
  * @param[in]  usernode    数据结点
  * @param[out] value       数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_static_set_find_next_value(jh_static_set_t* set, jh_static_set_node_type* usernode, void* value) {
    jh_static_set_node_type node = *(jh_static_set_node_type*)usernode;
    if(SGET(node, right) == SNULL) {
        while(SGET(node, parent) && (SSGET(node, parent, left) != node)) {
            node = SGET(node, parent);
        }
        node = SGET(node, parent);
        if(node) {
            JH_SET_MEMCPY(value, SGETE(node), set->datasize);
            *(jh_static_set_node_type*)usernode = node;
            return 0;
        }
        return -1;
    }
    
    node = SGET(node, right);
    while(SGET(node, left) != SNULL) {
        node = SGET(node, left);
    }
    JH_SET_MEMCPY(value, SGETE(node), set->datasize);
    *(jh_static_set_node_type*)usernode = node;
    return 0;
}

/**
  * @brief      在集合中查找上一个数据
  * @param[in]  set         集合
  * @param[in]  usernode    数据结点
  * @param[out] value       数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_static_set_find_prve_value(jh_static_set_t* set, jh_static_set_node_type* usernode, void* value) {
    jh_static_set_node_type node = *(jh_static_set_node_type*)usernode;
    if(SGET(node, left) == SNULL) {
        while(SGET(node, parent) && (SSGET(node, parent, right) != node)) {
            node = SGET(node, parent);
        }
        node = SGET(node, parent);
        if(node) {
            JH_SET_MEMCPY(value, SGETE(node), set->datasize);
            *(jh_static_set_node_type*)usernode = node;
            return 0;
        }
        return -1;
    }
    
    node = SGET(node, left);
    while(SGET(node, right) != SNULL) {
        node = SGET(node, right);
    }
    JH_SET_MEMCPY(value, SGETE(node), set->datasize);
    *(jh_static_set_node_type*)usernode = node;
    return 0;
}

/**
  * @brief      在集合中查找第一个大于或等于value数值的数据节点
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval     非0     成功
  * @retval     0       失败
  */
jh_static_set_node_type jh_static_set_lower_bound(jh_static_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return SNULL;
    
    jh_static_set_node_type node = set->root;
    if(node == SNULL)
        return node;
    
    jh_static_set_node_type retnode = SNULL;
    int ret = set->compare(value, SGETE(node));
    
    while (ret != 0) {
        node = ret < 0 ? retnode = node, SGET(node, left) : SGET(node, right);
        if(node == SNULL)
            break;
        
        ret = set->compare(value, SGETE(node));
    }
    
    return ret == 0 ? node : retnode;
}

/**
  * @brief      在集合中查找第一个大于value数值的数据节点
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval     非0     成功
  * @retval     0       失败
  */
jh_static_set_node_type jh_static_set_upper_bound(jh_static_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return SNULL;
    
    jh_static_set_node_type node = set->root;
    if(node == SNULL)
        return node;
    
    jh_static_set_node_type retnode = SNULL;
    int ret = set->compare(value, SGETE(node));
    
    while (1) {
        node = ret < 0 ? retnode = node, SGET(node, left) : SGET(node, right);
        if(node == SNULL)
            break;
        
        ret = set->compare(value, SGETE(node));
    }
    
    return retnode;
}

/**
  * @brief      在集合中查找第一个数据节点
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval     非0     成功
  * @retval     0       失败
  */
jh_static_set_node_type jh_static_set_begin(jh_static_set_t* set) {
    if(set == NULL)
        return SNULL;
    
    return jh_static_set_min(set, set->root);
}

/**
  * @brief      在集合中查找最后一个数据节点
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval     非0     成功
  * @retval     0       失败
  */
jh_static_set_node_type jh_static_set_end(jh_static_set_t* set) {
    if(set == NULL)
        return SNULL;
    
    return jh_static_set_max(set, set->root);
}

/**
  * @brief      获取集合的数据数量
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval     >=0     集合的数据数量
  */
size_t jh_static_set_count(jh_static_set_t* set) {
    if(set == NULL)
        return 0;
    
    return set->count;
}

/**
  * @brief      判断集合是否为空
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval      1      集合为空
  * @retval      0      集合不为空
  * @retval     -1      失败
  */
int jh_static_set_is_empty(jh_static_set_t* set) {
    if(set == NULL)
        return -1;
    
    return set->root == SNULL;
}

/**
  * @brief      判断集合是否已满
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval      1      集合已满
  * @retval      0      集合未满
  * @retval     -1      失败
  */
int jh_static_set_is_full(jh_static_set_t* set) {
    if(set == NULL)
        return -1;
    
    return SGET(SIDLEHEAD, right) == SNULL;
}

/**
  * @brief      在集合中查找数据
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval     非0     成功
  * @retval     0       失败
  */
jh_static_set_node_type jh_static_set_find(jh_static_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return SNULL;
    
    return jh_static_set_search(set, set->root, value);
}

/**
  * @brief      在集合中插入数据
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_static_set_insert(jh_static_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return -1;
    
    jh_static_set_node_type ret = jh_static_set_add(set, set->root, value);
    if(ret == SNULL)
        return -1;
    set->root = ret;
    set->count++;
    return 0;
}

/**
  * @brief      删除集合中的数据
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_static_set_erase(jh_static_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return -1;
    
    if(jh_static_set_search(set, set->root, value) == SNULL)
        return -1;
    
    set->root = jh_static_set_delete(set, set->root, value);
    set->count--;
    return 0;
}

/**
  * @brief      清空集合
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_static_set_clear(jh_static_set_t* set) {
    if(set == NULL)
        return -1;
    
    jh_static_set_destroy(set, set->root);
    set->root = SNULL;
    set->count = 0;
    return 0;
}

/**
  * @brief      集合初始化
  * @param[in]  set         集合
  * @param[in]  base        指向用于集合的数组
  * @param[in]  num         数组中能存放的数据项数量
  * @param[in]  size        每个数据项的大小
  * @param[in]  offset      数据项的地址偏移
  * @param[in]  datasize    每个用户数据的大小
  * @param[in]  dataoffset  用户数据的地址偏移
  * @param[in]  compare     指向用于比较两个数据的函数指针
  *
  * @return     errcode
  * @retval      0          成功
  * @retval     -1          失败
  */
int jh_static_set_init(jh_static_set_t* set, void* base, size_t num, size_t size, size_t offset, size_t datasize, size_t dataoffset, int (*compare)(const void*, const void*)) {
    if(set == NULL || compare == NULL)
        return -1;
    
    set->root = SNULL;
    set->count = 0;
    set->compare = compare;
    
    set->base = base;
    set->num = num;
    set->size = size;
    set->offset = offset;
    set->datasize = datasize;
    set->dataoffset = dataoffset;
    
    for (int i = 0; i < num; i++) {
        SGET(i, right) = i + 1;
    }
    
    SGET(SEND, right) = SNULL;
    
    return 0;
}
